#选择排序

**原理**  /*
每一次通过前后元素的比较，将待排序的元素中的最小/最大（排列顺序）的元素，放在序列的最后。

example: [4,2,1,3]
单次冒泡:  [4,2,1,3] > [2,4,1,3] > [2,1,4,3] > [2,1,3,4]
单次冒泡:  [2,1,3,4] > [1,2,3,4] > stop_flag=0 > break
*/

**核心**  /*
内循环中是前后元素(j, j+1)的比较、交换关系！
通过stop_flag来优化冒泡排序的提前终止
*/

**我的实现**
vector<int> LySort::bubbleSort(vector<int> &v) {
    // 1. 适当检查输入
    if (v.size() <= 1)
        return v;

    // 2. 两层循环，i循环代表冒泡的次数，j循环代表第i次冒泡需要交换j次
    vector<int> out = v;
    for (int i=0; i<v.size(); ++i) {
        // 3. 优化的终止条件，若某次冒泡没有改变元素顺序，则排列已经有序，可以结束
        int stop_flag = 1;
        for (int j=0; j<v.size()-i-1; ++j) {
            // 4. 在冒泡过程中，是前后元素(j, j+1)之间的交换，在某次冒泡结束后，最大/最小的元素一定位于最后
            if (out[j] > out[j+1]) { // increase
                std::swap(out[j], out[j+1]);
                stop_flag = 0;
            }
        }
        if (stop_flag)
            break;
    }
    return out;
}

**思考** /*
时间复杂度分析：
在不考虑提前终止的情况下，
第一次内循环(j)比较i-1次，然后是i-2次，i-3次，……，最后一次内循环比较1次。
共比较的次数是 (i-1) + (i-2) + ... + 1，求等差数列和，得 (i- 1 + 1)*i / 2 = i^2 / 2。
取最高项系数，因此时间复杂度为 O(N^2)

空间复杂度分析：
耗费的空间与输入数据大小无关，无论输入数据增大多少倍，不会耗费额外的空间进行排序（除了数组本身的空间）
因此时间复杂度为 O(1)

稳定性分析：
稳定的关键，在于排序完成后，相同元素的相对顺序是否变化。
冒泡排序能否稳定，关键在于 if (out[j] > out[j+1]) 中使用 > 或者 >=
如使用 >= 则会在相同元素之间执行交换的操作，导致不稳定
而使用 >  则不会出现相同元素之间的交换，稳定！

泛化性分析：
冒泡排序适用从大量的元素中选择一部分排序元素，例如从10000个元素中选择出大小为前10的元素
此时，外循环只需要设置i<10，即可在结束后在序列的尾部10个元素得到目标值
*/